import java.util.*;

/**
*	This is the base class used for each of the nearest-neighbor search method
*/
public abstract class NN
{
	/**
		This is an internal class mainly used to sort points based on distance to query
		It contains ID and distance of the points
		It implements interface "Comparable" mainly used for heap and java built-in sorting
	**/
	class SortingElement implements Comparable<SortingElement>
	{
		public int index;
		public Double value;
		
		public SortingElement(int index, Double value)
		{
			this.index = index;
			this.value = value;
		}

		public int compareTo(SortingElement other)
		{
			return ((value < other.value) ? -1 : 1);
		}
	}

	protected Point[] DataBase;
	protected int pointCount;	

	public NN(Point DataBase[])
	{
		this.DataBase = DataBase;
		pointCount = 0;
		if (DataBase != null) pointCount = DataBase.length;
	}

	public abstract SortingElement[] Query(Point q);

	/**
	 * This is a method to sort the point in database based on the distance to a reference point (p)
	 *  @param p a reference point
	 *  @param DataBase the points in the database
	 *  @return An array of of ID and distance to reference point sorted on distance to reference point
	**/
	protected SortingElement[] CreateSortedIndex(Point p, Point DataBase[])
	{
		SortingElement[] arr = new SortingElement[DataBase.length];
		int i,  j = 0;
		for (i = 0; i < DataBase.length && j < arr.length; i++)
		{
			arr[j++] = new SortingElement(i, p.Distance(DataBase[i]));
		}
		Arrays.sort(arr, 0, j);
		return arr;
	}
}
